\documentclass[UTF8]{ctexart}
\usepackage{listings} 
\usepackage{xcolor}
\usepackage{fancyhdr}%设置页脚页眉需要的包
\pagestyle{fancy}
\usepackage{graphicx}
\usepackage{cite}
\usepackage{booktabs}
\usepackage{tikz}
\documentclass{article}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{float}
\usepackage{amsthm}
\usepackage{xeCJK}
\usepackage{graphicx}
\usepackage{fullpage}
\usepackage{gnuplottex}
\usepackage{geometry}
\usepackage{enumitem}
\usepackage{verbatimbox}
\usepackage{amsfonts,amssymb} 
\usepackage[ruled,linesnumbered]{algorithm2e}
\usepackage[colorlinks,linkcolor=blue,citecolor=blue]{hyperref}
\usepackage{cite}
\CTEXsetup[format={\Large\bfseries}]{section}
\newtheorem{example}{例}             % 整体编号
\newtheorem{theorem}{定理}[section]  % 按 section 编号
\newtheorem{definition}{定义}
\newtheorem{axiom}{公理}
\newtheorem{property}{性质}
\newtheorem{proposition}{命题}
\newtheorem{lemma}{引理}
\newtheorem{corollary}{推论}
\newtheorem{remark}{注解}
\newtheorem{condition}{条件}
\newtheorem{conclusion}{结论}
\newtheorem{assumption}{假设}
\newcommand{\enabstractname}{Abstract}
\newenvironment{enabstract}{%
    \par\small
    \noindent\mbox{}\hfill{\bfseries \enabstractname}\hfill\mbox{}\par
    \vskip 2.5ex}{\par\vskip 2.5ex}
\usetikzlibrary{positioning, shapes.geometric}
\lstset{
  language=C++,
  frame=shadowbox,
  rulesepcolor=\color{red!20!green!20!blue!20},
  keywordstyle=\color{blue!90}\bfseries,
  commentstyle=\color{red!10!green!70}\textit,
  showstringspaces=false,
  numbers=left,
  numberstyle=\tiny,
  stringstyle=\ttfamily,
  breaklines=true,
  extendedchars=false,
  texcl=true}

\title{Theoretical Assignment I}

\author{韩骐骏 \\ (数学科学学院)信息与计算科学3200103585}

\begin{document}

\maketitle

\section{Problem 1.8.1 I}
\subsection{Problem Description}
Consider the bisection method starting with the initial interval [1.5,3.5]. In the following questions “the interval” refers to the bisection interval whose width changes across different loops.\\
\subsection{Question 1}
For interval [l, u], the width of the interval at the nth step is $\frac{u-l}{2^n}$, So by substituting the values of l and u, we can get the answer $$\frac{u-l}{2^n}=\frac{3.5-1.5}{2^n}=\frac{1}{2^n^-^1}$$

\subsection{Question 2}
From the way of iteration and the conditions for stopping iteration, it can be seen that the distance between the root and the midpoint of the interval can be infinitely close to half of the interval length.That is, when the iteration reaches a certain time, the interval is $[l_{\mbox{\scriptsize n}},u_{\mbox{\scriptsize n}}]$, and the upper bound of the distance from r to the midpoint of the interval is $\frac{u_{\mbox{\scriptsize n}}-l_{\mbox{\scriptsize n}}}{2}=\frac{1}{2^n}$. In particular, when $n=0$, the supremum of the distance between the root r and the midpoint of the interval is $1$.\\

\section{Problem 1.8.1 II}
\subsection{Problem Description}
In using the bisection algorithm with its initial interval as $[a_{\mbox{\scriptsize 0}},b_{\mbox{\scriptsize 0}}]$ with $a_{\mbox{\scriptsize 0}}>0$, we want to determine the root with its relative error no greater than $\epsilon$. Prove that this goal of accuracy is guaranteed by the following choice of the number of steps,$$n\geq \frac{\log(b_{\mbox{\scriptsize 0}}-a_{\mbox{\scriptsize 0}})-\log\epsilon-\log a_{\mbox{\scriptsize 0}}}{\log2}-1$$
\subsection{Proof}
According to the last part we know that the supremum of the distance between the root r and the midpoint of the interval at the nth step is $$\frac{u_{\mbox{\scriptsize n}}-l_{\mbox{\scriptsize n}}}{2}=\frac{b_{\mbox{\scriptsize 0}}-a_{\mbox{\scriptsize 0}}}{2^n^+^1}$$Thus the relative error is required that $$\frac{b_{\mbox{\scriptsize 0}}-a_{\mbox{\scriptsize 0}}}{2^n^+^1r}\geq\frac{b_{\mbox{\scriptsize 0}}-a_{\mbox{\scriptsize 0}}}{2^n^+^1a_{\mbox{\scriptsize 0}}}\geq\epsilon$$This inequality can be proved by simplifying it. It is worth noting that a hidden condition for this problem to be proved is $r\geq a_{\mbox{\scriptsize 0}}\geq 0$.\\

\section{Problem 1.8.1 III}
\subsection{Problem Description}
Perform four iterations of Newton’s method for the polynomial equation $p(x)=4x^3-2x^2+3=0$ with the starting point $x_{\mbox{\scriptsize 0}}=-1$. Use a hand calculator and organize results of the iterations in a table.\\
\subsection{Calculation results}
$p'(x)=12x^2-4x$,Thus the iterative formula is $$x_{\mbox{\scriptsize n+1}}=x_{\mbox{\scriptsize n}}-\frac{p(x_{\mbox{\scriptsize n}})}{p'(x_{\mbox{\scriptsize n}})}=x_{\mbox{\scriptsize n}}-\frac{4x_{\mbox{\scriptsize n}}^3-2x_{\mbox{\scriptsize n}}^2+3}{12x_{\mbox{\scriptsize n}}^2-4x_{\mbox{\scriptsize n}}}$$Now the calculated data is presented in the form of a table as follows.\\
\begin{table}[H]
\centering
\caption{Calculation results}
\label{tab:tableTab}
\begin{tabular}{cccccc} 
\toprule 
$n$ & 0 & 1 & 2 & 3 & 4 \\
\midrule 
$x_{\mbox{\scriptsize n}}$ & -1.0000 & −0.8125  & −0.7708 & −0.7688 & −0.7688 \\
\bottomrule 
\end{tabular}
\end{table}

\section{Problem 1.8.1 IV}
\subsection{Problem Description}
Consider a variation of Newton’s method in which only the derivative at $x_{\mbox{\scriptsize 0}}$ is used,$$x_{\mbox{\scriptsize n+1}}=x_{\mbox{\scriptsize n}}-\frac{f(x_{\mbox{\scriptsize n}})}{f'(x_{\mbox{\scriptsize 0}})}$$Find $C$ and $s$ such that $$e_{\mbox{\scriptsize n+1}}=Ce_{\mbox{\scriptsize n}}^s$$Where $e_{\mbox{\scriptsize n}}$ is the error of Newton’s method at step n, s is a constant, and $C$ may depend on $x_{\mbox{\scriptsize n}}$, the given function $f$ and its derivatives.
\subsection{Solution}
According to the mean value theorem, for each step, there is a $\xi_{\mbox{\scriptsize n}}$ between $x_{\mbox{\scriptsize n}}$ and $r$, such that $$f(x_{\mbox{\scriptsize n}})=f(r)+(x_{\mbox{\scriptsize n}}-r)f'(\xi_{\mbox{\scriptsize n}})=(x_{\mbox{\scriptsize n}}-r)f'(\xi_{\mbox{\scriptsize n}})$$By substitution we can get $$(x_{\mbox{\scriptsize n+1}}-r)=(x_{\mbox{\scriptsize n}}-r)-\frac{(x_{\mbox{\scriptsize n}}-r)f'(\xi_{\mbox{\scriptsize n}})}{f'(x_{\mbox{\scriptsize 0}})}=(x_{\mbox{\scriptsize n}}-r)(1-\frac{f'(\xi_{\mbox{\scriptsize n}})}{f'(x_{\mbox{\scriptsize 0}})})$$Therefore $C=1-\frac{f'(\xi_{\mbox{\scriptsize n}})}{f'(x_{\mbox{\scriptsize 0}})}$ and $s=1$.As $n\rightarrow\infty$, $C\rightarrow 1-\frac{f'(r)}{f'(x_{\mbox{\scriptsize 0}})}$.\\

\section{Problem 1.8.1 V}
\subsection{Problem Description}
Within $(-\frac{\pi}{2},\frac{\pi}{2})$, will the iteration $x_{\mbox{\scriptsize n+1}}=tan^-^1x_{\mbox{\scriptsize n}}$ converge?\\
\subsection{Solution}
It can be known from the function image that $$|x_{\mbox{\scriptsize n+1}}|=|tan^-^1x_{\mbox{\scriptsize n}}|\leq|x_{\mbox{\scriptsize n}}|$$And because $x=tan^-^1x$ when $x=0$, therefore convergence is considered.\\

\section{Problem 1.8.1 VI}
\subsection{Problem Description}
Let $p>1$. What is the value of the following continued fraction?$$x=\frac{1}{p+\frac{1}{p+\frac{1}{p+...}}}$$Prove that the sequence of values converges.\\
\subsection{Solution}
It is observed that the iteration method is $$x_{\mbox{\scriptsize 0}}=0,x_{\mbox{\scriptsize n+1}}=\frac{1}{p+x_{\mbox{\scriptsize n}}}$$Now we need to judge whether this iteration converges and what value it converges to.It can be known from the function image that this iteration converges. Thus let $x=\frac{1}{p+x},x>0$ and we find that $x=\frac{\sqrt{p^2+4}-p}{2}$.\\

\section{Problem 1.8.1 VII}
\subsection{Problem Description}
What happens in problem II if $a_{\mbox{\scriptsize 0}}<0<b_{\mbox{\scriptsize 0}}$? Derive an inequality of the number of steps similar to that in II. In this case, is the relative error still an appropriate measure?\\
\subsection{Solution}
Based on the solution of problem II, we can notice that it demands $|h|=|x_{\mbox{\scriptsize n}}-r|<\delta$ finally, thus it would be well that $$\frac{b_{\mbox{\scriptsize 0}}-a_{\mbox{\scriptsize 0}}}{2^n^+^1r}\leq\epsilon,\frac{b_{\mbox{\scriptsize 0}}-a_{\mbox{\scriptsize 0}}}{2^n^+^1}\leq\delta$$What only we can do is let $n\geq\frac{\log(b_{\mbox{\scriptsize 0}}-a_{\mbox{\scriptsize 0}})-\log\delta}{\log2}-1$ and verify the accuracy of the results obtained after iteration because $r$ may be close to $0$.\\

\end{document}
